1. Field of the Disclosure
This disclosure relates generally to concurrent programming, and more particularly to systems and methods for detecting and tolerating atomicity violations between concurrent code sections.
2. Description of the Related Art
Shared memory concurrent programming is becoming ubiquitous because of the ongoing influx of multi-core systems in mainstream computing environments. In such environments, a common means of communication between concurrent computations is via synchronized critical sections (or atomic blocks). However, correctly synchronizing access to shared memory is complicated, and is a source of some of the most difficult programming errors to solve in concurrent programs. One flavor of synchronization bugs in concurrent programs is atomicity violation bugs, such as those that are the result of a mismatch between the exact boundaries of critical sections required for the program to be correct (boundaries that disallow access interleaving that may lead to unexpected and/or incorrect program behavior), and the implementation of these boundaries in actual program code.
Data races are a well-known form of atomicity violation bugs. A concurrent program is said to have a data race when two or more threads access a shared memory location (with at least one access being a write) without synchronizing with each other. Such races can lead to unpredictable program behavior. Techniques to detect data races include type system support, extensive static analyses, and on-the-fly dynamic race detection techniques. Most of these approaches, other than the type system based approaches, tackle the race detection problem in one of two ways: happens-before analysis (in which the system determines a happens-before relationship between all shared memory accesses and synchronization points in the program, and assumes a data race in cases in which two memory accesses are not ordered by the happens-before relationship), and lock set analysis (in which the system dynamically maps each shared memory location to a set of locks, and infers a data race in situations in which a location is inconsistently protected by locks). There are advantages and disadvantages to each of these approaches. For example, the happens-before approach is precise, but extremely slow, and the lock set analysis approach is faster, but less precise. Some hybrid approaches improve upon these individual approaches, but are still far from being practically viable.
Some program analysis techniques have been used to determine blocks of code that are incorrectly unprotected by one or more locks, which can lead to data races. Another current technique uses static inference of critical sections to avoid atomicity violations. However, this approach restricts a critical section to just one define-use chain. Other atomicity violation detection tools track shared memory access interleavings, and establish specific invariants on what access interleavings are correct using trial runs of programs that are deemed to be correct. This tracking is expensive and results in orders of magnitude slowdowns during execution time. Still other techniques take a hardware-centric approach, such as leveraging bulk memory disambiguation hardware to inflate atomically executed blocks of code, or leveraging the memory protection hardware available in commodity processors.